package com.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

import org.testng.annotations.Test;

public class WordLadder2 {
	public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        ArrayList res = new ArrayList();
        HashMap<String, HashSet<String>> map = new HashMap();
        HashMap<String, Integer> visited = new HashMap<String, Integer>();
        ArrayDeque<Ladder> queue = new ArrayDeque<Ladder>();
        
        queue.add(new Ladder(start, 1));
        visited.put(start, 1);
        
        int min = Integer.MAX_VALUE;
        boolean found = false;
        while (!queue.isEmpty()) {
        	Ladder next = queue.remove();
        	if (next.step + 1 > min) break;
        	
        	String word = next.key;
			for (int j=0; j<word.length(); j++) {
				char[] ch = word.toCharArray();
				char cur = ch[j];
				for (char i='a'; i<='z'; i++) {
					if (i == cur) continue;
					ch[j] = i;
					String newWord = new String(ch);
					if (dict.contains(newWord) && 
						(!visited.containsKey(newWord) || visited.get(newWord) == next.step + 1 )) {
						if (newWord.equals(end)) {
							min = next.step + 1;
							found = true;
						}
						if (!visited.containsKey(newWord)) queue.add(new Ladder(newWord, next.step + 1));
						visited.put(newWord, next.step + 1);
						add(map, word, newWord);
					}
				}
			}
        }
        
        if (!found) return res;
        
        ArrayList<String> list = new ArrayList<String>();
        list.add(end);
        res.add(list);
        
        while (!((ArrayList<String>)res.get(0)).get(0).equals(start)) {
        	ArrayList temp = new ArrayList();
        	while (res.size() > 0) {
	        	ArrayList<String> curList = (ArrayList<String>) res.remove(0);
	        	String word = curList.get(0);
	        	HashSet<String> from = map.get(word);
	        	
	        	for (String s : from) {
	        		ArrayList<String> seq = new ArrayList<String>();
	        		seq.add(s);
	        		seq.addAll(curList);
	        		temp.add(seq);
	        	}
	        }
        	res.clear();
	        res = temp;
        }
        
        return res;
    }
	
	private void add(HashMap<String, HashSet<String>> map, String from, String to) {
		if (!map.containsKey(to)) map.put(to, new HashSet<String>());
		map.get(to).add(from);
	}
	
	private class Ladder {
		String key;
		int step;
		public Ladder(String key, int step) {
			this.key = key;
			this.step = step;
		}
	}
	
	@Test
	public void test1() {
		HashSet<String> dict = new HashSet<String>();
		dict.add("hot");
		dict.add("cog");
		dict.add("dog");
		dict.add("tot");
		dict.add("hog");
		dict.add("hop");
		dict.add("pot");
		dict.add("dot");
		findLadders("hot", "dog", dict);
	}
}
